#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/1 18:28
# @USER    : Shengji He
# @File    : ContainerWithMostWater.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai).
        n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
        Find two lines, which together with x-axis forms a container, such that the container contains the most water.

        :param height: List[int]
        :return: int

        Note: You may not slant the container and n is at least 2.

        Example:
            Input: [1,8,6,2,5,4,8,3,7] \n
            Output: 49
        """
        # output = max([max([min([height[j], height[i]]) * abs(i - j)  for j in range(1, len(height))])
        # for i in range(len(height) - 1)])
        output = 0
        s, e = 0, len(height) - 1
        while s < e:
            output = max([output, min(height[e], height[s]) * (e - s)])
            if height[s] < height[e]:
                s += 1
            else:
                e -= 1

        return output


if __name__ == '__main__':
    S = Solution()
    sample = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    print(S.maxArea(sample))
    print('done')
